package leetcode;

class NumMatrix {
    private int[][]sum;

    public static void main(String[] args) {
        int[][]matirx={{3,0,1,4,2},{5,6,3,2,1},{1,2,0,1,5},{4,1,0,1,7},{1,0,3,0,5},};
        NumMatrix numMatrix = new NumMatrix(matirx);
       // System.out.println(Arrays.toString(numMatrix.sum[0]));
        System.out.println(numMatrix.sumRegion(2, 1, 4, 3));

    }

    public NumMatrix(int[][] matrix) {
        //初始化
        sum=new int[matrix.length][matrix[0].length];
        sum[0][0]=matrix[0][0];
        for(int i=1;i<sum[0].length;++i){
            sum[0][i]=matrix[0][i]+sum[0][i-1];
        }
        for(int i=1;i<sum.length;++i){
            sum[i][0]=sum[i-1][0]+matrix[i][0];
        }
        //其他元素的遍历
        for(int i=1;i<sum.length;++i){
            for(int j=1;j<sum[0].length;++j){
                sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sum[row2][col2]-sum[row2][col1-1]-sum[row1-1][col2]+sum[row1-1][col1-1];
    }
}